package jianzhioffer.tree;

import algorithm.model.TreeNode;

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 重建二叉树
 * 描述：输入某二叉树的前序遍历和中序遍历结果，重建出该二叉树（假设输入的遍历结果中都不含重复的数字）
 *
 * 思路：
 * 1、root.pre = [root.val] + [left.pre] + [right.pre]
 *      先序的数列，第一个必定是根节点。跟在后面的，分别是左子树的先序数列，和右子树的先序数列
 * 2、root.in = [left.in] + [root.val] + [right.in]
 *      取出这个节点的值，在中序数列里，找到这个值。那么在中序数列里，这个值左边的，是左子树的中序遍历，右边的值，是右子树的中序遍历。
 * 3、上面两个完成以后，可以分别找到左子树和右子树的 先序和中序子数列。
 * 4、递归调用，完成树的构建
 *
 * Created by yzy on 2020-04-26 17:21
 */
public class ReConstructBinaryTree {

    public static void main(String[] args) {
        int[] arr = new int[]{1,2,3,4,5,6,7,8};
        List<Integer> list = Arrays.stream(arr).boxed().collect(Collectors.toList());
        System.out.println(list.indexOf(3));

        int[] pre = new int[]{1,2,4,7,3,5,6,8};
        int[] in = new int[]{4,7,2,1,5,3,8,6};
        TreeNode node = reConstructBinaryTree(pre, in);
        System.out.println(node);
    }

    public static TreeNode reConstructBinaryTree(int [] pre, int [] in) {
        List<Integer> preList = Arrays.stream(pre).boxed().collect(Collectors.toList());
        List<Integer> inList = Arrays.stream(in).boxed().collect(Collectors.toList());
        return getNode(preList, inList);
    }


    public static TreeNode getNode(List<Integer> pre, List<Integer> in){
        if(pre==null){
            return null;
        }

        int currVal = pre.get(0);
        TreeNode node = new TreeNode(currVal);
        if(pre.size() == 1){
            return node;
        }

        int inListIdx = in.indexOf(currVal);
        int leftSize = inListIdx - 0;
        int rightSize = in.size() - inListIdx - 1;
        if(leftSize != 0){
            node.left = getNode(pre.subList(1,leftSize+1), in.subList(0,leftSize));
        }
        if(rightSize != 0){
            node.right = getNode(pre.subList(leftSize+1,pre.size()), in.subList(leftSize+1, in.size()));
        }
        return node;
    }
}
